import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/*
解题思路：后序非递归遍历需要借助栈
 1. 空树，直接返回
 2. 如果树非空：从根节点位置开始遍历，但此时根节点不能遍历，因为后序遍历规则：左子树、右子树、根节点
      a. 沿着根节点一直往左走，将所经过路径中的节点依次入栈
      b. 取栈顶元素，该元素取到后，其左子树要么为空，要么已经遍历，
         但是此时该节点不能遍历，除非其右子树不存在或者其右子树已经遍历，才可以遍历该节点
         如果该节点右子树没有遍历，将其右子树作为一棵新的二叉树遍历，继续a
具体实现：参考代码，学生自己动手画图理解
*/
class Solution2 {
    public List<Integer> postorderTraversal(TreeNode root) {
        // 如果是空树，直接返回
        List<Integer> ret = new ArrayList<>();
        if(null == root){
            return ret;
        }
        TreeNode cur = root;
        TreeNode prev = null;  // 记录刚刚过节点的前一个
        Stack<TreeNode> s = new Stack<>();
        while(null != cur || !s.empty()){
            // 找以cur为根的最左侧节点，并保存其所经路径中所有的节点
            while(cur != null){
                s.push(cur);
                cur = cur.left;
            }
            // 此处不能直接遍历根，根节点的右子树遍历完成之后才可以遍历根
            TreeNode top = s.peek();
            // 如果根节点的右子树是空，或者右子树已经遍历过了
            if(top.right == null || top.right == prev){
                ret.add(top.val);
                prev = top;
                s.pop();
            }
            else
            {
                // 如果top的右子树存在，并且没有遍历过，将其右子树当成新树遍历
                cur = top.right;
            }
        }
        return ret;
    }
}